package hot_100;

import com.sun.source.tree.Tree;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * @author: Darven
 * @createTime: 2025-10-03  18:39
 * @description: TODO
 */
public class P226 {

    public static void main(String[] args) {
        // 构建测试二叉树:     4
        //                  /   \
        //                 2     7
        //                / \   / \
        //               1   3 6   9
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        System.out.println("翻转前:");
        printTree(root);

        // 调用翻转函数
        new P226().invertTree(root);

        System.out.println("翻转后:");
        printTree(root);
    }

    // 中序遍历打印树节点
    private static void printTree(TreeNode root) {
        if (root != null) {
            printTree(root.left);
            System.out.print(root.val + " ");
            printTree(root.right);
        }
    }

    // 广度优先搜索，一层一层的进行转化
//    public TreeNode invertTree(TreeNode root) {
//        if(root==null) return null;
//        Queue<TreeNode> queue=new ArrayDeque<>();
//
//        queue.offer(root);
//
//        while(!queue.isEmpty()){
//            TreeNode node = queue.poll();
//            TreeNode left=null,right=null;
//            if(node.left!=null){
//                queue.offer(node.left);
//                left=node.left;
//            }
//            if(node.right!=null){
//                queue.offer(node.right);
//                right=node.right;
//            }
//            // 节点调换
//            node.left=right;
//            node.right=left;
//        }
//
//        return root;
//    }

    // 递归
    public TreeNode invertTree(TreeNode root) {
        res(root);
        return root;
    }

    private void res(TreeNode root){
        if(root==null) return;

        TreeNode left = root.left;
        TreeNode right = root.right;

        root.left=right;
        root.right=left;

        res(left);
        res(right);
    }
}
